package com.gaogzhen.datastructure.queue;

import java.io.Serializable;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 基于链表实现的队列
 * @author Administrator
 * @version 1.0
 * @description 链表队列
 * @date 2022-11-02 21:08
 */
public class LinkQueue<E> implements Queue<E>, Serializable {

    /**
     * 队头
     */
    private Node<E> first;

    /**
     * 队尾
     */
    private Node<E> last;

    /**
     * 队列元素个数
     */
    private int size;

    public LinkQueue() {
    }

    /**
     * 元素入队(队尾）
     * @param e 元素
     */
    @Override
    public void offer(E e) {
        Node<E> l = last;
        last = new Node<>(e, null);
        if (first == null) {
            first = last;
        } else {
            l.next = last;
        }
        size++;
    }

    /**
     * 查看队头元素
     * @return  队头元素
     */
    @Override
    public E peek() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return first.item;
    }

    /**
     * 队头元素出队
     * @return  队头元素
     */
    @Override
    public E poll() {
        if (first == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node<E> f = first;
        E item = f.item;
        first = f.next;
        f.item = null;
        if (first == null) {
            last = null;
        } else {
            f.next = null;
        }
        size--;
        return item;
    }

    /**
     * 判断队列是否为空
     * @return {@code true} 队列为空时，否则
     *         {@code false}
     */
    @Override
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 返回队列元素个数
     * @return  队列元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 节点类
     * @param <E>   泛型
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    @Override
    public Iterator<E> iterator()  {
        return new LinkedIterator(first);
    }

    @Override
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e);
            if (! it.hasNext()) {
                return sb.append(']').toString();
            }
            sb.append(',').append(' ');
        }
    }

    /**
     * 迭代器
     */
    private class LinkedIterator implements Iterator<E> {
        private Node<E> current;

        public LinkedIterator(Node<E> first) {
            current = first;
        }

        @Override
        public boolean hasNext()  { return current != null;                     }

        /**
         * 基于队列只在队头删除元素的特点，这里不实现
         */
        @Override
        public void remove()      { throw new UnsupportedOperationException();  }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E item = current.item;
            current = current.next;
            return item;
        }
    }
}
